import compiler

def next(c, t):
    """Takes char (c) and transition table (t), returns indexes of possible states as table nexts."""

    nexts = []

    # iterate over transition functions and search for matching chars
    for tf in t:

        # if not a reject-all state
        if len(tf) > 0:

            # if found matching char
            if (c == tf[0] or tf[0] == '.'):

                # (stop and) return index of new state
                nexts.append(tf[1])

    # reached end of transition table

    # found no matching char
    if len(nexts) < 1:

        # add rejecting state
        nexts.append(0)

    return nexts


def accept(cs, fas, v=False, i=1):
    """Takes input chars (cs), list of finite automatas (fas), verbose mode (v, defaults to False) and index of first state (defaults to 1). Returns True if state-run accepts input chars, False else"""

    # finite automata states as tables of possible states (Thompson!)
    fass = []
    for notneeded in xrange(len(fas)):
        fass.append(i)

    if v:
        print('testing \'' + cs + '\' against regex ' + fas[0][2]),

        if len(fas) > 1:
            for z in xrange(len(fas)-1):
                print('or ' + fas[z+1][2]),

        print('\n'),

    # iterate over characters in input
    for c in cs:

        # next phase always copies current fas to newfas and possible states to
        # newfass
        newfas = []
        newfass = []

        # iterate over finite automata
        for i, fa in enumerate(fas):

            nexts = next(c, fa[0][fass[i]])

            # make as many copies as there are possible states
            for ns in nexts:

                # ... skipping rejecting states
                if ns != 0:

                    # copy automata, copy (index of) state
                    newfas.append(fa)
                    newfass.append(ns)

        # move to next char with "new" automata and states
        fas = newfas
        fass = newfass

    # reached end of input, but have we reached an accepting state?
    for i, fa in enumerate(fas):

        # skip automata in state 0 (reject)
        if (fass[i] != 0):

            # iterate over accepting states and see if final state of current
            # finite automata matches any of them
            for acc in fa[1]:
                if (fass[i] == acc):
                    return True

    # despite all efforts, input was faulty
    return False


def acceptfile(fn, fas, v=False):
    """Takes file name fn, set of finite automatas fas (and verbosity indicator v), returns hits with hits[0] being the line number that hit was found, hits[1] the number of hits in line and hits[2] the line as string."""

    hits = []

    with open(fn) as f:

        # index for counting lines
        i = 1

        # go through lines in file
        for l in f:

            if l[-1] == '\n':
                # remove line feed
                l = l[:-1]

            # split line into words (at spaces)
            ws = compiler.split(l, ' ')

            nhits = 0

            for w in ws:
                if accept(w, fas, v):
                    nhits = nhits+1

            # first internal cell indicates line number
            # second indicates number of hits in line
            # third indicates whole line as string
            hits.append([i, nhits, l])

            # moving on
            i = i+1

    return hits


def concat(fa1, fa2):
    """Concatenates two FA:s, compiles new FA and returns result."""

    # Takes string representations of automata, concatenates and (re-)compiles
    # them. Very inefficient at the moment.

    newfa = ''

    for a1 in fa1:
        for a2 in fa2:
            newfa = newfa + a1[2] + '|' + a2[2]

    print(newfa)
    return compiler.comp(newfa)

def union(fa1, fa2):
    """Applies fa1|fa2 and returns it."""

    # append each fa in fa2 in fa1
    for fa in fa2:
        fa1.append(fa)

    return fa1

def p(fas):
    """A function for printing a set of finite automatas."""
    for fa in fas:
        p2(fa)

def p2(fa):
    """A function for printing finite automata fa."""

    print('')
    print('Regex \'' + fa[2] + '\'')
    print('States:')

    i = 0

    while i < len(fa[0]):

        a = False

        # overly complicated loop for finding out whether fa[0][i] is accepting
        # state
        for acc in fa[1]:

            # accepting state
            if (i == acc):
                a = True
                print(str(i) + '. state: ' + str(fa[0][i]) + ' (accept)')

        # not an accepting state
        if not a:
            print(str(i) + '. state: ' + str(fa[0][i]))

        i = i+1

    print('')



# BEGIN TESTING MATERIAL

"""

# t - transitions: t[0] is input char, t[1] is new state
t0 = [] # reject state, no transitions (returns 0 on all input)
t1 = [['a', 2], ['b', 3]]
t2 = [['a', 1], ['b', 3]]
t3 = [['b', 3]]

# ss - states: s[0] is reject state
ss1 = [t0, t1, t2, t3]

# fa - finite automata: fa[0] states, fa[1] accepting states
fa1 = [ss1, [3], '*a*b']

# TODO: fa as object??


print(fa1)
print(accept('aab', fa1)) # fa1 accepts
print(accept('aaba', fa1)) # fa1 rejects


fa2 = compiler.comp('yuh.')
p(fa2)
print(accept('yuh', fa2, True))
print(accept('yuho', fa2, True))
print(accept('yuhot', fa2, True))


fa3 = compiler.comp('....')
print(fa3)
print(accept('yuh', [fa3]))
print(accept('yuho', [fa3]))
print(accept('yuhot', [fa3]))



fa4 = compiler.comp('*a')
print(fa4)
print(accept('b', [fa4], True))
print(accept('aaaaa', [fa4], True))


fa5 = compiler.comp('*a*b')
p(fa5)
print(accept('bbb', fa5, True))
print(accept('aaaaa', fa5, True))
print(accept('aaaaab', fa5, True))

p(concat(fa2, fa5))

p(compiler.comp('a\\*b'))

fa6 = compiler.comp('?a?b')
p(fa6)
print(accept('a', fa6, True))
print(accept('b', fa6, True))
print(accept('c', fa6, True))
print(accept('ba', fa6, True))
print(accept('aaabbb', fa5,fa2, True))
print(accept('aaba', fa5,fa2, True))
print(accept('yuho', fa5,fa2, True))

"""
